package com.leetcode.a004;

import java.awt.*;
import java.util.Arrays;

/**
 * @author zhengqn
 * @Title: FindMedian
 * @Description: 忽略时间复杂度的算法
 * @date 2019/12/30 10:55
 */
public class FindMedian {
    private static final int EVEN = 2;
    /**
     * 如果不考虑复杂度的话
     */
    public double findMedian(int[] nums1, int[] nums2) {
        // 先合并两个数组得到新的数组
        int[] newArray = mergeArrays(nums1, nums2);
        int len = newArray.length;
        if (len % EVEN != 0) {
            //长度为奇数
            return newArray[len/2];
        }else{
            //长度为偶数
            double d1 = newArray[len/2-1];
            double d2 = newArray[len/2];
            return (d1+d2)/2;
        }


    }

    /**
     * 传入的是两个有序数组，合并返回新的有序数组
     */
    public int[] mergeArrays(int[] nums1, int[] nums2){
        int len = nums1.length + nums2.length;
        int[] re = new int[len];
        int z = 0;
        int i = 0;
        int j = 0;
        while(i < nums1.length || j < nums2.length){
            if(i < nums1.length && j < nums2.length) {
                if (nums1[i] < nums2[j]) {
                    re[z++] = nums1[i++];
                }else{
                    re[z++] = nums2[j++];
                }
            }else if(i < nums1.length){
                re[z++] = nums1[i++];
            }else{
                re[z++] = nums2[j++];
            }
        }
        return re;
    }

    public static void main(String[] args) {
        FindMedian F = new FindMedian();

        int[] nums1 = new int[]{1, 3, 5};
        int[] nums2 = new int[]{2, 4};
        int[] mergeArrays = F.mergeArrays(nums1, nums2);

        System.out.println(Arrays.toString(mergeArrays));
        System.out.println(F.findMedian(nums1, nums2));
    }
}
